package com.leetcode.algorithm.y22.m09.w3;

/**
 * 670. 最大交换
 * 
 * https://leetcode.cn/problems/maximum-swap/
 * 
 * @author jie.deng
 *
 */
class Question0670Solution01 {

	public int maximumSwap(int num) {
		char[] chars = ("" + num).toCharArray();
		int len = chars.length;
		int sep = -1;
		// 算法步骤：
		// 1.找第1个大于左边的位sep
		// 2.从sep到尾[sep,...)，找最大值所在的位right
		// 3.从头到sep[0,...sep)，找第1个小于right的位left
		// 4.交换left和right
		for (int i = 1; i < len; i++) {
			if (chars[i] - chars[i - 1] > 0) {
				sep = i;
				break;
			}
		}
		if (sep == -1) {
			// 已经是逆序数
			return num;
		}
		int right = sep;
		for (int i = sep + 1; i < len; i++) {
			if (chars[i] - chars[right] >= 0) {
				right = i;
			}
		}
		for (int left = 0; left < sep; left++) {
			if (chars[left] - chars[right] < 0) {
				char tmp = chars[left];
				chars[left] = chars[right];
				chars[right] = tmp;
				break;
			}
		}
		return Integer.parseInt(String.valueOf(chars));
	}

}